package LeetCode.leetcode148;

import java.util.HashMap;

class Solution {
    public ListNode sortList(ListNode head) {
        HashMap<Integer, ListNode> map = new HashMap<>();
        map.get()
        ListNode virtualHead = new ListNode(), p = head;
        while (p != null) {
            //找到插入位置
            ListNode resCur = virtualHead.next, resPre = virtualHead;
            while (resCur != null) {
                if (resCur.val >= p.val) {
                    break;
                }else{
                    resPre = resCur;
                    resCur = resCur.next;
                }
            }
            ListNode tmp = resPre.next;
            ListNode cur = new ListNode(p.val);
            resPre.next = cur;
            cur.next = tmp;
            p = p.next;
        }
        return  virtualHead.next;
    }
}